The present invention relates to computer graphics, and more particularly, to a method and apparatus reducing the complexity of objects in a 3-D virtual environment.
Interactive computer graphics systems produce realistic-looking, three-dimensional models and are useful for applications such as architectural and mechanical computer aided design (CAD), flight simulation, and virtual reality. Such graphics systems typically include a computer workstation that displays images of a three-dimensional model on a video screen as seen from a simulated observer""s viewpoint that can be interactively controlled by the user. Ever since the introduction of computer graphics, there has been an ongoing demand to produce more realistic and interactive images. The term, xe2x80x9creal-time,xe2x80x9d is commonly used to describe interactive and realistic image processing systems. In a xe2x80x9creal-timexe2x80x9d system, the user should perceive a continuous motion of objects in a scene. For example, in a video game having real-time capabilities, the active characters and view point should respond with minimal delay to a user""s inputs, and should move smoothly. To produce such real-time effects, an image rendering system has to generate a new image at a sufficiently high rate such that the user perceives continuous motion of objects in a scene. The rate at which a new image is computed for display is referred to as the xe2x80x9ccomputationalxe2x80x9d rate or the xe2x80x9ccomputational framexe2x80x9d rate. The computational rate needed to achieve realistic effects can vary depending on how quickly objects move about the scene and how rapidly the viewing perspective changes. For a typical application, a real-time graphics system recomputes a new image at least ten times a second to generate a series of images that simulate continuous motion. For high-quality animation applications, however, the computational rate may be significantly higher. It is generally desired that such graphics systems maintain an interactive frame rate that is substantially constant (e.g., twelve frames per second).
One problem associated with typical graphics processing devices is the memory required to store the bitmap for even a single image. For example, the system may require 3.75 megabytes (Mb) of random access memory to support a display resolution of 1280xc3x971024 (i.e., number of pixel columns and rows) and 24 bits of color information per pixel. This information, which again represents the image of a single screen, is stored in a portion of the computer""s display memory known as a frame buffer.
The demands placed upon the system are further exacerbated by the complexity of the information that often must be processed to render an image from the object stored. For example, the modeling of a three-dimensional surface is, in itself, a complex task. While a curved surface can be represented by a mesh of planar polygons, the xe2x80x9csmoothnessxe2x80x9d of its appearance in the rendered image will depend both upon the resolution of the display and the number of individual polygons that are used to model the surface. Consequently, the computations associated with high resolution modeling of complex surfaces based upon polygon meshes can be extremely resource intensive.
In conventional graphics systems, an object or scene is scanned and an image of it is otherwise digitized and stored in the system as a set of data points relating to position, texture, and color. The scanned image is tessellated into sets of object elements such as polygons (typically triangles), which in the aggregate approximate the shape of the original object or scene (generally, the geometry) to the degree of resolution of the imaging and storage properties of the system. Although modem modeling systems used in CAD virtual reality and other forms of modem animation are expanding their geometric domain to include free form surfaces, polygonal models remain the primary 3D representation used in the manufacturing, architectural, mechanical, and entertainment industries. Polygonal models are particularly effective for hardware assisted rendering, which is important for mechanical, architectural, virtual reality, and electronic mock-up applications involving complex CAD models.
These complex three-dimensional models routinely consist of hundreds or thousands of polygons. Even a relatively simple CAD model of an oil tank consisting of less than 25 parts can contain nearly 20,000 separate polygons. As the simulated observer""s interactive viewpoint changes (e.g., rotating the oil tank and zooming in on certain portions of the tank), objects can enter or leave the simulated field of view, or can be occluded from view by other objects. As introduced above, conventional graphics systems typically include a frame buffer. To generate an image, the graphic system renders all of the objects in a scene and stores the resulting image in this frame buffer. The system then transfers the rendered image data to a display. In a conventional graphics architecture, the entire frame buffer is erased and the scene is re-rendered to create a next frame""s image. In this type of system, every object must be redrawn for each frame because the frame buffer is cleared between frames. Every object therefore is updated at the same rate, regardless of its actual motion in the scene or its importance to the particular application. This can often lead to a perceptible xe2x80x9cpoppingxe2x80x9d display effect. For this reason, it is desirable to provide the capability of rendering the model such that a sufficiently detailed image can be displayed to an observer and a smooth visual transition occurs between two representations of the same image.
U.S. Pat. No. 5,590,248 to Zarge et al. discloses a method for reducing the complexity of a polygonal mesh representative of the surface of an object to be displayed. The patent discloses a process of removing co-planar vertices and polygons from a polygonal mesh, but does not disclose the capability to identify and remove round cuts of a predetermined size from a CAD model. Zarge simply discloses the process of identifying co-planar vertices and polygons, removing them and then re-triangulating the opening left by the removal of the vertices and polygons.
In summary, prior art techniques do not adequately address the problem of satisfactorily rendering a solid CAD model. There is a need to overcome these and other problems of the prior art and to provide an efficient method for optimizing the display of CAD models. The present invention, as illustrated in the following description, is directed to solving one or more of the problems set forth above.
In accordance with the present invention, a method for reducing the complexity of a triangulated CAD model is disclosed. In operation, the method identifies a plurality of coplanar vertices in a CAD model, removes the coplanar vertices if they form a circle of a predetermined size, and then triangulates an opening left by the removal of the vertices from the CAD model.
In accordance with another aspect of the present invention, a machine-readable storage medium is provided having stored thereon machine executable instructions. The execution of the instructions is adapted to implement a method for reducing the complexity of a triangulated CAD model. The method includes identifying a plurality of co-planar vertices in the model, removing the plurality of vertices from the model provided that the plurality of vertices form a circle of a predetermined size, and triangulating an opening left by removing the plurality of vertices from the model.
In accordance with yet another aspect of the present invention, an apparatus for reducing the complexity of a triangulated CAD model is disclosed. The apparatus comprises a network device having a memory containing a program that includes several modules. A module is provided for identifying a plurality of co-planar vertices in a triangulated CAD model. A module is provided for removing a plurality of vertices from the triangulated CAD model, provided the plurality of vertices form a circle of a predetermined size. A module is also provided for triangulating an opening left by the removal of the plurality of vertices from the triangulated CAD model.